package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/symmetric-tree/
 */
public class _101_对称二叉树 {
    /*
方法二：迭代
首先我们引入一个队列，
这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。
每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），
然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
*/
    Queue<TreeNode> queue = new LinkedList<>();

    public boolean isSymmetric(TreeNode root) {
        queue.offer(root);
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if (node1 == null && node2 == null) continue;
            if ((node1 == null || node2 == null) || (node1.val != node2.val)) return false;
            queue.offer(node1.left);
            queue.offer(node2.right);

            queue.offer(node1.right);
            queue.offer(node2.left);
        }
        return true;

    }

    /**
     * 我们可以实现这样一个递归函数，
     * 通过「同步移动」两个指针的方法来遍历这棵树，
     * pp 指针和 qq 指针一开始都指向这棵树的根，
     * 随后 pp 右移时，qq 左移，pp 左移时，qq 右移。
     * 每次检查当前 pp 和 qq 节点的值是否相等，如果相等再判断左右子树是否对称。
     */
    public boolean isSymmetric1(TreeNode root) {
        return check(root, root);
    }

    boolean check(TreeNode pp, TreeNode qq) {
        if (pp == null && qq == null) return true;
        if ((pp == null || qq == null) || (pp.val != qq.val)) return false;
        return check(pp.left, qq.right) && check(pp.right, qq.left);
    }
}
